Automated carpooling systems have been used to match potential drivers having cars that are willing to carpool with one or more passengers who are seeking rides. In existing carpooling systems potential drivers and passenger submit messages, notifications, or other entries to the carpooling system. These entries may include a starting or pickup location, an ending or dropoff location, a date/time range during which the traveling may occur, a passenger capacity of the driver's vehicle, and a maximum travel time the driver is willing to accept during carpooling.
FIG. 1 shows an exemplary road map 100 showing a highway, represented by the two parallel lines and an assortment of streets, represented by the single lines. The highway may have a speed limit that is twice the speed of the streets. The map 100 also shows the starting locations of a carpool driver 110, five passengers 141 to 145, and an office 150, which may be the final destination for all of the participants 110 and 141 to 145 in this example.
Existing carpooling systems have used optimization algorithms to match drivers and passengers. These existing optimization algorithms calculated the road distance that a carpool driver has to travel in order to reach each of the passengers seeking a ride. The existing algorithms may then calculate an estimated travel time for the carpool driver to reach each passenger by applying an expected speed or speed limit to the calculated road distance in order to calculate the travel time.
FIG. 2 shows an example of how road distances have been calculated in the past. In FIG. 2, road distances were calculated from each route 201, 202, 203, 205, and 206 between the driver 110 and each of the passengers 141 to 145, and then each route to the office 150 from the passengers 141 to 145. Thus, route 201 would be used to calculate the road distance between driver 110 and passenger 141. Thereafter, a route 204 from passenger 141 to the office 150 would be determined to calculate the additional road distance from passenger 141 to office 150, and then calculate a total road distance for picking up passenger 141.
Route 202 would be used to calculate the road distance between driver 110 and passenger 142. Thereafter, a route from passenger 142 to the office 150 would be determined to calculate the additional road distance from passenger 142 to office 150, and then calculate a total road distance for picking up passenger 142. The process would then continue for each of the other passengers 143 to 145.
In addition to calculating the total road distances for picking up each passenger, the algorithms also calculated the estimated travel times for picking up each passenger. These estimated travel times were calculated by applying an expected vehicle speed, which may be based on a known speed limit, to the calculated road distances. The estimated travel times would then be compared to the maximum travel time the driver is willing to accept to determine whether it is feasible for the carpool driver to pickup and dropoff the passenger within the maximum travel time window provided by the driver.
For drivers who have the capacity to accept more than one passenger, the system would then continue the calculations to calculate the total road distances and travel times for picking up different combinations of passengers up to the capacity of the carpool driver's vehicle. The calculated travel times would then be compared to the maximum travel time the driver is willing to accept to determine whether it is feasible for the carpool driver to pickup and dropoff each combination of passengers within the maximum travel time window provided by the driver.
Performing each of the calculations in situations where there are many drivers and many passengers becomes computationally intensive. This is part because the system must first identify the shortest road distances and/or travel times between each of the points. This may involve checking several different route options for each set of points. As the number of drivers, passenger, and vehicle capacities increases, the number of calculations required may increase exponentially. With hundreds of passengers and drivers with different passenger capacities, the number of the calculations to be performed has slowed response times to the point where the system can no longer process changes in real time or even near real time.
In existing carpooling systems, the carpooling system may present a user with a list of carpooling options and the user may manually select one of the carpooling options. Thereafter, changes may be submitted if a user or other participant is no longer able to participate in the scheduled carpool. For example, a carpool participant may get sick or have a meeting rescheduled and therefore may need to cancel and/or reschedule a carpool. In existing carpooling systems, the carpool participants who are no longer able to participate in the carpool would have to manually notify each of the other participants of the cancellation or rescheduling. Thereafter, the carpool system would search for alternative carpool assignment options that would still be acceptable to the remaining participants. Once the system found alternative carpool assignment options, the system would notify each of the participants of the new carpool options.
In the past, if one of several passengers in an assigned carpool submits a cancellation, the carpool system would notify each of the other passengers that the carpool was cancelled. Thereafter, the carpool system would search for alternative carpool assignments, and often ended up presenting the same carpooling option to the remaining passengers and the original carpool driver, though without the passenger who submitted the cancellation. Thus, in the span of several minutes, the remaining passengers and the driver would initially receive a notification that the carpool assignment was cancelled, and then subsequently receive a notification that they could choose the same carpool assignment, though this time without the canceling passenger. Users of the carpooling system found this to be frustrating and undesirable.
Also, in the past, if a participant in an assigned carpool submits a request to reschedule the carpool to a different time, the carpool system would notify each of the passengers in the assigned carpool that the carpool was cancelled. Thereafter, the carpool system would search for alternative carpool assignments, and would often end up notifying the passengers and the driver that the same carpool was available at the rescheduled time, provided that the rescheduled time was minor and within an acceptable traveling time period of the other participants. Thus, in the span of several minutes, each of the passengers and the driver would initially receive a notification that the carpool assignment was cancelled, and then subsequently receive a notification that the same cancelled carpool was still available, though at the rescheduled time. Users of the carpooling system found this to be frustrating and undesirable.
There is a need for large scale carpooling systems to perform calculations more efficiently to enable the processing of carpooling requests in real time or near real time. There is also a need for carpooling systems to automatically assign carpool participants to carpools and avoid sending unnecessary cancellation notifications to carpool participants when processing cancellation and/or rescheduling requests.